package leetcode.D300.T300;

import java.util.Arrays;

class Solution {
//    public int lengthOfLIS(int[] nums) {
//        int[] dp = new int[nums.length];
//        Arrays.fill(dp, 1);
//        for(int i=0; i<nums.length; ++i) {
//            for(int j=0; j<i; ++j) {
//                if(nums[i] > nums[j]) {
//                    dp[i] = Math.max(dp[i], 1+dp[j]);
//                }
//            }
//        }
//        int result = 0;
//        for(int i=0; i<dp.length; ++i) {
//            result = Math.max(result, dp[i]);
//        }
//        return result;
//    }

    // 二刷
    /*public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for(int i=0; i<nums.length; ++i) {
            for(int j=0; j<i; ++j) {
                if(nums[i] > nums[j]) {
                    dp[i] = Integer.max(dp[i], dp[j]+1);
                }
            }
        }
        int result = 0;
        for(int i=0; i<nums.length; ++i) {
            result = Integer.max(result, dp[i]);
        }
        return result;
    }*/

    // 三刷
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for(int i=1; i<nums.length; ++i) {
            for(int j=0; j<i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        int result = 1;
        for(int i=0; i<nums.length; ++i) {
            result = Math.max(dp[i], result);
        }
        return result;
    }
}
